'''
@see c09_heap

'''
import random


def heap_insert(nums, i):
    while (parent := (i - 1) // 2) >= 0 and nums[i] > nums[parent]:
        nums[i], nums[parent] = nums[parent], nums[i]
        i = parent

def heapify(nums, i, size):
    while (l := i * 2 + 1) < size:
        r = l + 1
        best_child = r if (r < size and nums[r] > nums[l]) else l
        best = best_child if nums[best_child] > nums[i] else i
        if best == i:
            break
        nums[i], nums[best] = nums[best], nums[i]
        i = best


def heap_sort(nums):
    if not nums or (n := len(nums)) < 2: return
    # 插入构建大跟堆
    # 1log2 + 2log4 + 4log8 + 8log16 + ...
    for i in range(n):
        heap_insert(nums, i)
    # 进行size轮，每次将最大的元素，放在最后一位，并将堆的size-1
    # nlogn + (n-1)log(n-1) + ... + 1log1
    for i in range(n - 1, -1, -1):
        nums[0], nums[n-1] = nums[n-1], nums[0]
        heapify(nums, 0, n-1)
        n -= 1
def heap_sort2(nums):
    if not nums or (n := len(nums)) < 2: return
    # heapify构建大跟堆， 在每个子树建堆，最后整个树建好堆
    # O(n): 比如最后一层64个节点
    #   最坏情况= 64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
    #           = 0(n/2) + 1(n/4) + 2(n/8) + 3(n/16) +  ... + [ log(n)(n/2^log(n)) 即 log(n)]
    for i in range(n-1, -1, -1):
        heapify(nums, i, n)
    # nlogn + (n-1)log(n-1) + ... + 1log1
    for i in range(n - 1, -1, -1):
        nums[0], nums[n-1] = nums[n-1], nums[0]
        heapify(nums, 0, n-1)
        n -= 1


n = 10
nums = [random.randint(-100, 100) for _ in range(n)]
print(nums)
heap_sort2(nums)
print(nums)